import { IHeap } from './types'
import ArrayList from '@/sources/ArrayList'
import { threadId } from 'worker_threads';


/**
 * 二叉堆 (分为大顶堆和小顶堆)
 */
export default class Heap<T = number> implements IHeap<T> {
    private al: ArrayList<T>;
    constructor(elements: Array<T> = [], public compartor = (a: T, b: T) => ((a as any) - (b as any))) {
        // 初始化动态数组
        this.al = new ArrayList<T>()
        // 初始时批量建堆
        this.al.createArray(elements)
        elements.length > 0 && this.heapify()
    }

    /**
     * 获取二叉堆数量
     */
    size() {
        return this.al.size()
    }

    /**
     * 判断二叉堆是否为空
     */
    isEmpty() {
        return this.size() === 0
    }

    /**
     * 清空二叉堆
     */
    clear() {
        this.al.clear()
    }


    /**
     * 添加元素
     * @param element 
     */
    add(element: T) {
        // 校验参数
        this.checkElement(element);
        // 添加元素
        this.al.add(element);

        // 上滤
        this.upper(this.size() - 1);
    }

    /**
     * 获取堆顶元素
     */
    get() {
        return this.al.get(0)
    }


    /**
     * 删除堆顶元素
     */
    remove() {
        // 获取该元素
        const oldVal = this.al.get(0);
        const last = this.size() - 1

        // 最后一个元素上来
        this.al.arr[0] = this.al.array[last]

        // 将最后元素值为undefined
        this.al.array[last] = undefined as any

        // 长度减一
        this.al.descSize();

        // 下滤
        this.down()
        // 返回要删除的元素
        return oldVal
    }

    /**
     * 替换堆顶元素
     * @param element 
     */
    replace(element: T) {
        // 获取该元素
        const oldVal = this.al.get(0);
        // 替换该元素
        this.al.set(0, element)
        // 下滤
        this.down()
        // 返回要删除的元素
        return oldVal
    }

    /**
     * 校验元素
     * @param element 
     */
    private checkElement(element: T) {
        if (element == null) throw new Error('元素不合法~~')
    }

    /**
     * 上滤
     * @param index 
     */
    private upper(index: number) {
        // debugger
        if (index <= 0) return;
        // 父元素的索引
        let parI = this.getParI(index);
        // 没有父元素
        if (parI < 0) return;
        // debugger
        while (parI >= 0) {
            // 父元素存在
            const min = this.getMin(index, parI)
            if (min === index) {
                // 比父元素小，交换两个元素的位置
                this.al.swap(index, parI);
                // 改变parI和index
                index = parI
                parI = this.getParI(parI)
            } else {
                // 比父元素小，直接结束循环
                break;
            }
        }
    }

    /**
     * 下滤
     * @param i 从哪个位置开始下滤
     * @param d 是否删除导致的下滤
     */
    private down(i = 0) {
        // 从0 开始下溢出

        // 获取数量
        const sizes = this.size();

        // 非叶子节点的数量
        const half = sizes >> 1;

        // 遍历完非叶子节点
        while(i < half) {
            // 获取左右孩子
            const lI = this.getLeftChild(i),
                  rI = this.getRightChild(i);

            // 获取左右的
            const minI = this.getMin(lI, rI);

            // i都比左右孩子小，直接结束循环
            if (this.getMin(i, minI) === i) {
                break;
            }

            // 交换
            this.al.swap(minI, i)

            // 更换MinI
            i = minI
        }
    }

    /**
     * 批量建堆
     */
    heapify() {
        const sizes = this.size()
        // 1. 自上而下的上滤 （比作添加）[1, size)
        // for (let i = 1; i < sizes; i++) {
        //     this.upper(i)
        // }


        // 2. 自下而上的下滤（比作删除）  从非叶子节点开始， [size >> 1 - 1, 0]
        let i = sizes >> 1 - 1;
        for (; i >= 0; i --) {
            this.down(i)
        }

    }


    /**
     * 获取父元素的索引
     * @param i 
     */
    private getParI(i: number) {
        return ~~((i - 1) >> 1)
    }

    /**
     * 获取左子节点的索引
     * @param i 
     */
    private getLeftChild(i: number) {
        return ((i + 1) << 1) - 1
    }

    /**
     * 获取右子节点的索引
     * @param i 
     */
    private getRightChild(i: number) {
        return (i + 1) << 1
    }

    /**
     * 获取左右中的最小值
     * @param l 
     * @param r 
     */
    private getMin(l: number, r: number) {
        let ld = this.al.get(l)
        let rd = this.al.get(r);

        // 右为空，直接返回左即可
        if (rd == undefined) return l
        return this.compartor(ld, rd) < 0 ? l : r 
    }

    /**
     * 
     * @param cb 
     */
    forEach(cb: (ele: T, i: number) => void) {
        this.al.forEach((e, i) => {
            cb(e, i!)
            return false
        })
    }

}